#include <stdio.h>
#include <vector>
#include <fcntl.h>
#include <io.h>

#define DEBUG 0

unsigned int b ;

unsigned int hasNext( FILE *fp ) {

  static unsigned int index = 8 ;
  static int buffer ;

  if( index >= 8 ) {
    buffer = fgetc( fp ) ;
    if( buffer == EOF )
      return 0 ;
    index = 0 ;
  }

  b = buffer & 1 ;
  buffer >>= 1 ;
  index++ ;

  return 1 ;

}

unsigned int next( ) {
  return b ;
}

unsigned int valid( FILE *fp ) {
  fseek( fp, 0, SEEK_CUR ) ;
  if( ! hasNext( fp ) )
    return 0 ;
  if( ! next( ) )
    return 0 ;  

  if( ! hasNext( fp ) )
    return 0 ;
  if( ! next( ) )
    return 0 ;  

  if( ! hasNext( fp ) )
    return 0 ;
  if( next( ) )
    return 0 ;  

  return 1 ;

}

int nextBit( FILE *fp, int data ) {
  if( ! hasNext( fp ) )
    return -1 ;
  data = ( data << 1 ) | ( next( ) & 1 ) ;
  return data ;
}

int getNextData( FILE *fp ) {

  int data = 0 ;
  for( unsigned int i = 0; i < 7; i++ ) {
    if( ( data = nextBit( fp, data ) ) < 0 ) {
      return -1 ;
    }
  }

  if( ( data & 0x78 ) == 0x18 || ( data & 0x60 ) == 0x20 || ( data & 0x60 ) == 0x40 ) {
    if( ( data = nextBit( fp, data ) ) < 0 ) {
      return -1 ;
    }
    return data - 0x30 ;
  }

  if( ( data & 0x7c ) == 0x64 || ( data & 0x70 ) == 0x70 ) {
    if( ( data = nextBit( fp, data ) ) < 0 ) {
      return -1 ;
    }
    if( ( data = nextBit( fp, data ) ) < 0 ) {
      return -1 ;
    }
    return data - 0x190 + 0x90 ;
  }

  if( ( data & 0x70 ) == 0x00 || ( data & 0x78 ) == 0x10 ) {
    return data + 0x100 ;
  }

  if( ( data & 0x7c ) == 0x60 ) {
    if( ( data = nextBit( fp, data ) ) < 0 ) {
      return -1 ;
    }
    return data - 0xc0 + 0x118 ;
  }

  return -1 ;

}

int _getExt( FILE *fp, unsigned int count ) {

  int data = 0 ;
  for( unsigned int i = 0; i < count; i++ ) {
    if( ! hasNext( fp ) )
      return -1 ;
    data |= ( next( ) << i ) ;
  }
  return data ;

}

int getExt( FILE *fp, int value ) {

  if( value >= 0x00 && value <= 0x1d ) {
    unsigned int count = 0 ;
    if( value <= 3 )
      count = 0 ; 
    else
      count = ( value / 2 ) - 1 ;
    return _getExt( fp, count ) ;
  } else if( value >= 0x101 && value <= 0x11d ) {
    unsigned int count = 0 ;
    if( value <= 264 )
      count = 0 ;
    else
      count = ( ( value - 257 ) / 4 ) - 1 ;
    return _getExt( fp, count ) ;
  }

  return -1 ;

}

int getDistance( FILE *fp ) {

  int data = 0 ;
  for( unsigned int i = 0; i < 5; i++ ) {
    data = nextBit( fp, data ) ;
  }
  return data ; 

}

void pushQueue( std::vector< int > *q, int c ) {
  while( q->size( ) >= 32 * 1024 ) {
    printf( "%c", q->at( 0 ) ) ;
    q->erase( q->begin( ) ) ;
  }
  q->push_back( c ) ;
}

void copyPasteQueue( std::vector< int > *q, unsigned int distance, unsigned int length ) {
  for( unsigned int i = 0; i < length; i++ ) {
    pushQueue( q, q->at( q->size( ) - distance ) ) ;
  }
}

void flushQueue( std::vector< int > *q ) {
  while( ! q->empty( ) ) {
    printf( "%c", q->at( 0 ) ) ;
    q->erase( q->begin( ) ) ;
  }
}

unsigned int calcLength( unsigned int value, unsigned int ext ) {
  if( value == 285 )
    return 258 ;

  unsigned int base = value - 257 ;
  if( base < 8 )
    return base + 3 ;

  unsigned int count = ( base / 4 ) - 1 ;
  unsigned int pow = 1 ;
  for( unsigned int i = 0; i < count; i++ ) {
    pow *= 2 ;
  }

  return pow * 4 + ( base - ( 8 + 4 * ( count - 1 ) ) ) * pow + ext + 3 ;
 
}

unsigned int calcDistance( unsigned int value, unsigned int ext ) {
  if( value < 4 )
    return value + 1 ;

  unsigned int count = ( value / 2 ) - 1 ;
  unsigned int pow = 1 ;
  for( unsigned int i = 0; i < count; i++ ) {
    pow *= 2 ;
  }

  return pow * 2 + ( value - ( 4 + 2 * ( count - 1 ) ) ) * pow + ext + 1 ;
}

unsigned int execute( FILE *fp, std::vector< int > *q, unsigned int value ) {

  if( value < 0x100 ) {
    if( DEBUG )
      printf( "%c\n", value ) ;
    pushQueue( q, value ) ;
  } else if( value == 0x100 ) {
    return 0 ;
  } else if( value <= 0x11d ) {
    unsigned int ext = getExt( fp, value ) ;
    unsigned int distance = getDistance( fp ) ;
    unsigned int ext2 = getExt( fp, distance ) ;
    if( DEBUG )
      printf( "\nd=%d, l=%d\n", calcDistance( distance, ext2 ), calcLength( value, ext ) ) ;
    copyPasteQueue( q, calcDistance( distance, ext2 ), calcLength( value, ext ) ) ;
  }

  return 1 ;

}

int main( int argc, char **argv ) {

  FILE *fp ;

  if( argc != 2 ) {
    printf( "usage: %s <input file name>\n", argv[ 0 ] ) ;
    return -1 ;
  }

  if( ! ( fp = fopen( argv[ 1 ], "rb" ) ) ) {
    printf( "can't open input file %s\n", argv[ 1 ] ) ;
    return -1 ;
  }

  if( ! valid( fp ) ) {
    printf( "this data may not be deflate data.\n" ) ;
    fclose( fp ) ;
    return -1 ;
  }

  setmode( fileno( stdout ), O_BINARY ) ;

  std::vector< int > q ;
  int value ;
  while( ( value = getNextData( fp ) ) >= 0 ) {
    if( ! execute( fp, &q, value ) )
      break ;
  }

  flushQueue( &q ) ;
  fclose( fp ) ;

  return 0 ;
}

